/*
 * @lc app=leetcode.cn id=41 lang=typescript
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
function firstMissingPositive(nums: number[]): number {
  const m = nums.length;
  // 将元素交换到正确的索引位置上
  for (let i = 0; i < m; i++) {
    while (nums[i] !== i + 1) {
      // 值超出区间，不做交换操作
      if (nums[i] <= 0 || nums[i] > m) break;
      let idx = nums[i] - 1;
      // 交换双方相同，不做处理
      if (nums[i] === nums[idx]) break;
      // 交换元素
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
    }
  }
  let ans = 0;
  // 如果当前元素和索引不匹配，跳出循环
  while (ans <= m && nums[ans] === ans + 1) {
    ans++;
  }
  return ans + 1;
}
// @lc code=end
